/**
 * https://leetcode.cn/submissions/detail/565047098/
 * 1482. 制作 m 束花所需的最少天数
 * Medium, 黄伟杰 2024.9.16
 * 二分查找
 */

#include <bits/stdc++.h>
using namespace std;

class Solution
{
    bool check(vector<int> &bloomDay, int mid, int m, int k)
    {
        int fl = 0;  // 朵数
        int shu = 0; // 有几束
        for (int i = 0; i < bloomDay.size() && shu < m; i++)
        {
            if (bloomDay[i] <= mid)
            {
                fl++;
                if (fl == k)
                {
                    fl = 0;
                    shu++;
                }
            }

            else
                fl = 0;
        }
        return shu >= m;
    }

public:
    int minDays(vector<int> &bloomDay, int m, int k)
    {
        if (m > bloomDay.size() / k)
            return -1;
        vector<int> a = bloomDay;
        sort(a.begin(), a.end());
        int low = a[0], higt = a.back(), ans;
        while (low <= higt)
        {
            int mid = (low + higt) / 2;
            if (check(bloomDay, mid, m, k))
            {
                ans = mid;
                higt = mid - 1;
            }
            else
                low = mid + 1;
        }
        return ans;
    }
};